/*
 * @lc app=leetcode.cn id=114 lang=cpp
 *
 * [114] 二叉树展开为链表
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode * root){
    if(root == nullptr) return ;

    flatten(root->left);
    flatten(root->right);

    TreeNode * left = root->left;
    TreeNode * right = root->right;

    root->left = nullptr;
    root->right = left;

    TreeNode * p = root;
    while(p->right != nullptr){
        p = p->right;
    }
    p->right = right;

}

    // void flatten(TreeNode* root) {
    //     if(root == nullptr) return ;

    //     flatten(root->left);
    //     flatten(root->right);

    //     /**** 后续遍历位置 ****/
    //     //1、左右子树已经被拉成一条直线
    //     TreeNode *left = root->left;
    //     TreeNode *right = root->right;

    //     //将左子树作为右子树
    //     root->left = nullptr;
    //     root->right = left;

    //     //将原先的右子树接到当前右子树的末端

    //     TreeNode *p = root;
    //     while(p->right != nullptr){
    //         p = p->right; 
    //     }
    //     p->right = right;
        
    // }
};
// @lc code=end

// 定义：将以 root 为根的树拉平为链表
// void flatten(TreeNode root) {
//     // base case
//     if (root == null) return;

//     flatten(root.left);
//     flatten(root.right);

//     /**** 后序遍历位置 ****/
//     // 1、左右子树已经被拉平成一条链表
//     TreeNode left = root.left;
//     TreeNode right = root.right;

//     // 2、将左子树作为右子树
//     root.left = null;
//     root.right = left;

//     // 3、将原先的右子树接到当前右子树的末端
//     TreeNode p = root;
//     while (p.right != null) {
//         p = p.right;
//     }
//     p.right = right;
// }

void flatten(TreeNode * root){
    if(root == nullptr) return ;

    flatten(root->left);
    flatten(root->right);

    TreeNode * left = root->left;
    TreeNode * right = root->right;

    root->left = nullptr;
    root->right = left;

    TreeNode * p = root;
    while(p.right != nullptr){
        p = p.right;
    }
    p.right = right;

}